package JZOffer;

// 两个链表的第一个公共节点
public class JzOffer52 {
    // 双指针
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode h1 = headA;
        ListNode h2 = headB;

        while (h1 != h2) {
            h1 = h1 == null ? headB : h1.next;
            h2 = h2 == null ? headA : h2.next;
        }
        return h1;
    }


    ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        int sizeA = 0;
        int sizeB = 0;

        ListNode curA = headA;
        ListNode curB = headB;
        while (curA != null) {
            curA = curA.next;
            sizeA++;
        }
        while (curB != null) {
            curB = curB.next;
            sizeB++;
        }

        if (sizeA > sizeB) {
            for (int i = 0; i < sizeA-sizeB; i++) {
                headA = headA.next;
            }
        } else {
            for (int i = 0; i < sizeB-sizeA; i++) {
                headB = headB.next;
            }
        }
        while (headA != headB && headA != null) {
            headA = headA.next;
            headB = headB.next;
        }
        return headA;
    }
}
